#include <bits/stdc++.h>

using namespace std;

// 合并K个有序链表
// 牛客测试链接：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
// 力扣测试链接：https://leetcode.cn/problems/merge-k-sorted-lists/

// 不要提交这个类
struct ListNode 
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};


class Solution 
{
private:
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 创建一个小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        // 让所有的头结点进入小根堆
        for(auto l : lists)
        {
            if(l) heap.push(l);
        }
        
        if(heap.empty()) return nullptr;

        // 先弹出一个节点，做总头部
        ListNode* head = heap.top();
        ListNode* tail = head;
        if(head->next) heap.push(head->next);
        heap.pop();
        while(!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            tail->next = t;
            tail = t;
            if(t->next) heap.push(t->next);
        }

        return head;
    }
};


// 归并分支的做法
class Solution 
{
private:
    // 合并两个有序链表
    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        ListNode* newHead = new ListNode(0), *tail = newHead;
        ListNode* cur1 = head1, *cur2 = head2;
        while(cur1 && cur2)
        {
            if(cur1->val < cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }

        tail->next = cur1 ? cur1 : cur2;

        cur1 = newHead->next;
        // delete newHead;
        return cur1;
    }

    // 将 [left, right] 范围内的链表合并成一个有序链表
    ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right)
    {
        if(left == right) return lists[left];
        if(left > right) return nullptr;

        int mid = left + (right - left) / 2;
        ListNode* l = mergeKLists(lists, left, mid);
        ListNode* r = mergeKLists(lists, mid + 1, right);

        return merge(l, r);
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        return mergeKLists(lists, 0, lists.size() - 1);
    }
};